#ifndef __GREEDY_H__
#define __GREEDY_H__
#define OBJECT_ORIENTED 0
#if OBJECT_ORIENTED
#include <cassert>
#include <iostream>
#include <list>

//define a class called "item" which has the properties include weight and price
class Item{
public:
	Item():weight_(0),price_(0){};
	Item(int weight, int price):weight_(weight),price_(price){};
	int GetWeight() const{
		return weight_;
	}
	int GetPrice() const{
		return price_;
	}
	double GetPricePerWeight() const{
		assert(0 != weight_);
		return static_cast<double>(price_) / weight_;
	}
	bool operator<(const Item& other) const{
		return this->GetPricePerWeight() < other.GetPricePerWeight();
	}
	bool operator>(const Item& other) const{
		return this->GetPricePerWeight() > other.GetPricePerWeight();
	}
	bool operator==(const Item& other) const{
		return this->GetPricePerWeight() == other.GetPricePerWeight();
	}
private:
	int weight_;
	int price_;
};

 using namespace std;
 
class Greedy{
 public:
	 //Test the Knapsack-Greedy Algorithm
	 static void KnapsackTestDrive(){
		Item i(2,10),i2(3,5),i3(5,15),i4(7,7),i5(1,6),i6(4,18),i7(1,3);
		list<Item> itemList;
		itemList.push_back(i);
		itemList.push_back(i2);
		itemList.push_back(i3);
		itemList.push_back(i5);
		itemList.push_back(i6);
		itemList.push_back(i7);
		itemList.sort();
		list<pair<Item,double> > pack;
		int MaxLimit = 15;
		double temp = 0;
		for(;;){
			if(itemList.empty() || temp >= MaxLimit) break;
			if(temp + itemList.back().GetWeight() <= MaxLimit){
				pack.push_back(std::make_pair(itemList.back(),1));
				temp += itemList.back().GetWeight();
				itemList.pop_back();
			}else {
				double diff = MaxLimit - temp;
				pack.push_back(std::make_pair(itemList.back(), diff / itemList.back().GetWeight()));
				temp += diff;
				itemList.pop_back();
			}
		}

		double total = 0.0;
		for(;;){
			if(pack.empty()) break;
			cout << "weight: "<<pack.front().first.GetWeight()
				 <<" price: " <<pack.front().first.GetPrice() 
				 << " percent: "<< pack.front().second<<endl;
			total += pack.front().first.GetPrice()*pack.front().second;
			pack.pop_front();
		}
		cout <<"total :" << total <<endl;
	 }
};
#else 
#include <stdlib.h>
#define MAX 1000
struct item{
	int size;
	int value;
};

item items[5];

int knap(int cap){
	static int known[MAX];
	int max = 0, space, temp;
	if(known[cap] != 0) return known[cap];
	for(int i = 0 ; i < 5; ++i){
		if((space = cap - items[i].size) >= 0){
			if(max < ( temp = items[i].value + knap(space))){
				max = temp;
			}
		}
	}
	return known[cap] = max;
}

void Test(){
	items[0].size = 3;
	items[0].value = 4;
	items[1].size = 4;
	items[1].value = 5;
	items[2].size = 7;
	items[2].value = 10;
	items[3].size = 8;
	items[3].value = 11;
	items[4].size = 9;
	items[4].value = 13;

	printf("%d",knap(17));
}
#endif
#endif